/**
 * @addtogroup BAS
 * @{
 * @file
 * HashMap容器操作
 */
#include <assert.h>
#include <string.h>
#include "bas/bas_hash_map.h"

static const char mcaId[] = "$Id$";

//表示被删除的HashMapSlot的Magic Number
static void *gpvDummy = NULL;
#define HASH_SLOT_REMOVED &gpvDummy

//判断HashMapSlot是否空闲
#define IS_HASH_MAP_SLOT_EMPTY(_tHashMapSlot) ((_tHashMapSlot).pvKey == HASH_SLOT_REMOVED || (_tHashMapSlot).pvKey == NULL)

//扰动移位Magic Number
#define PERTURB_SHIFT 5

static bool _basHashMapIteratorIsValid(const T_Iterator tIterator);
static void _basHashMapIteratorGetValue(const T_Iterator tIterator, void *pvValue);
static void *_basHashMapIteratorGetPointer(const T_Iterator tIterator);
static T_Iterator _basHashMapIteratorNext(const T_Iterator tIterator);
static bool _basHashMapIteratorEqual(const T_Iterator tFirstIterator, const T_Iterator tSecondIterator);

static int _basHashMapExpand(T_HashMap *ptHashMap);
static void _basHashMapRemoveHashSlot(T_HashMap *ptHashMap, T_HashMapSlot *ptHashMapSlot);
static unsigned int _basHashMapGetHashValue(const T_HashMap *ptHashMap, const void *pvKey);
static int _basHashMapCompareKey(const T_HashMap *ptHashMap, const void *pvKey1, const void *pvKey2);
static T_HashMapSlot *_basHashMapSearchHashSlot(const T_HashMap *ptHashMap, const unsigned int uiHashValue,
                                                const void *pvKey);

//HashMap迭代器回调函数表
static T_IteratorCallBackTable mtHashMapIteratorCallBackTable =
    {_basHashMapIteratorIsValid,
     _basHashMapIteratorGetValue,
     _basHashMapIteratorGetPointer,
     NULL,  //T_IteratorSetValueFunction not support
     _basHashMapIteratorNext,
     NULL,  //T_IteratorPrevFunction not support
     _basHashMapIteratorEqual,
     NULL,  //T_IteratorLessFunction not support
     NULL,  //T_IteratorNextNFunction not support
     NULL,  //T_IteratorPrevNFunction not support
     NULL}; //T_IteratorMinusFunction not support

BAS_EXPORT unsigned int basHashMapDefaultHash(const void *pvKey, const size_t nKeyLength)
{
    //使用times33算法
    unsigned int uiHashValue = 0;
    const char *pcKey = (const char *)pvKey;

    for (size_t i = 0; i < nKeyLength; ++i)
    {
        //hash = hash * 33 + pcKey[i]
        uiHashValue = (uiHashValue << 5) + uiHashValue + pcKey[i];
    }

    return uiHashValue;
}

BAS_EXPORT T_HashMap *_basHashMapCreate(const T_TypeInfo tKeyTypeInfo, const T_TypeInfo tValueTypeInfo, ...)
{
    T_HashMap *ptHashMap = NULL;
    va_list varList;

    if (NULL == (ptHashMap = (T_HashMap *)malloc(sizeof(T_HashMap))))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return NULL;
    }
    memset(ptHashMap, 0, sizeof(T_HashMap));

    //迭代器回调函数表
    ptHashMap->ptCallBackTable = &mtHashMapIteratorCallBackTable;
    //关键字的类型信息
    memcpy(&ptHashMap->tKeyTypeInfo, &tKeyTypeInfo, sizeof(ptHashMap->tKeyTypeInfo));
    //值的类型信息
    memcpy(&ptHashMap->tValueTypeInfo, &tValueTypeInfo, sizeof(ptHashMap->tValueTypeInfo));

    //可变参数为用户定义的Hash函数, 如未提供使用默认Hash函数
    va_start(varList, tValueTypeInfo);
    if (BAS_PARM_END == (ptHashMap->pfnHash = va_arg(varList, T_HashFunction)))
    {
        ptHashMap->pfnHash = basHashMapDefaultHash;
    }
    va_end(varList);

    //分配HashMapSlot, 初始化HashMap
    if (NULL == (ptHashMap->taHashMapSlot = 
                 (T_HashMapSlot *)malloc(sizeof(T_HashMapSlot) * BAS_HASH_MAP_INIT_SIZE)))
    {
        free(ptHashMap);
        CONTAINER_LOG_ERROR("malloc failed");
        return NULL;
    }
    memset(ptHashMap->taHashMapSlot, 0,
           sizeof(T_HashMapSlot) * BAS_HASH_MAP_INIT_SIZE);

    ptHashMap->uiMask = BAS_HASH_MAP_INIT_SIZE - 1;
    ptHashMap->uiLimit = (unsigned int)(BAS_HASH_MAP_INIT_SIZE * BAS_HASH_MAP_LOAD_FACTOR);
    ptHashMap->uiUsed = 0;

    return ptHashMap;
}

BAS_EXPORT void basHashMapDestroy(T_HashMap *ptHashMap)
{
    if (NULL == ptHashMap)
    {
        return;
    }
    
    basHashMapClear(ptHashMap);
    free(ptHashMap->taHashMapSlot);
    free(ptHashMap);
}

BAS_EXPORT void basHashMapClear(T_HashMap *ptHashMap)
{
    assert(ptHashMap != NULL);    

    for (unsigned int i = 0; i < ptHashMap->uiMask + 1; ++i)
    {
        if (!IS_HASH_MAP_SLOT_EMPTY(ptHashMap->taHashMapSlot[i]))
        {
            _basHashMapRemoveHashSlot(ptHashMap, &ptHashMap->taHashMapSlot[i]);
        }
        ptHashMap->taHashMapSlot[i].pvKey = NULL;
        ptHashMap->taHashMapSlot[i].pvValue = NULL;
    }
    ptHashMap->uiUsed = 0;
}

BAS_EXPORT size_t basHashMapSize(const T_HashMap *ptHashMap)
{
    assert(ptHashMap != NULL);    

    return ptHashMap->uiUsed;
}

BAS_EXPORT bool basHashMapEmpty(const T_HashMap *ptHashMap)
{
    assert(ptHashMap != NULL);

    return basHashMapSize(ptHashMap) == 0;
}

BAS_EXPORT int basHashMapInsert(T_HashMap *ptHashMap, ...)
{
    assert(ptHashMap != NULL);

    T_HashMapSlot tHashMapSlot;
    T_HashMapSlot *ptHashMapSlotFind = NULL;
    va_list varList;

    //存放的键值对到达上限, 需要扩大HashMap
    if (ptHashMap->uiUsed >= ptHashMap->uiLimit)
    {
        if (_basHashMapExpand(ptHashMap) != 0)
        {
            CONTAINER_LOG_ERROR("_basHashMapExpand failed");
            return -1;
        }
    }

    memset(&tHashMapSlot, 0, sizeof(tHashMapSlot));

    //为新插入的键值对分配内存
    if (NULL == (tHashMapSlot.pvKey = malloc(ptHashMap->tKeyTypeInfo.nTypeSize)))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return -1;
    }
    if (NULL == (tHashMapSlot.pvValue = malloc(ptHashMap->tValueTypeInfo.nTypeSize)))
    {
        free(tHashMapSlot.pvKey);
        CONTAINER_LOG_ERROR("malloc failed");
        return -1;
    }

    //从可变参数取值
    //---取关键字
    va_start(varList, ptHashMap);
    if (_basContainerGetVaArgValue(&ptHashMap->tKeyTypeInfo, tHashMapSlot.pvKey, &varList) != 0)
    {
        free(tHashMapSlot.pvKey);
        free(tHashMapSlot.pvValue);
        CONTAINER_LOG_ERROR("_basContainerGetVaArgValue failed");
        return -1;
    }
    //---取值
    if (_basContainerGetVaArgValue(&ptHashMap->tValueTypeInfo, tHashMapSlot.pvValue, &varList) != 0)
    {
        free(tHashMapSlot.pvKey);
        free(tHashMapSlot.pvValue);
        CONTAINER_LOG_ERROR("_basContainerGetVaArgValue failed");
        return -1;
    }
    va_end(varList);

    tHashMapSlot.uiHashValue = _basHashMapGetHashValue(ptHashMap, tHashMapSlot.pvKey);
    ptHashMapSlotFind = _basHashMapSearchHashSlot(ptHashMap, tHashMapSlot.uiHashValue, tHashMapSlot.pvKey);

    if (!IS_HASH_MAP_SLOT_EMPTY(*ptHashMapSlotFind))
    {
        _basHashMapRemoveHashSlot(ptHashMap, ptHashMapSlotFind);
    }

    memcpy(ptHashMapSlotFind, &tHashMapSlot, sizeof(T_HashMapSlot));
    ++ptHashMap->uiUsed;

    return 0;
}

BAS_EXPORT int basHashMapErase(T_HashMap *ptHashMap, ...)
{
    assert(ptHashMap != NULL);

    T_HashMapSlot *ptHashMapSlotFind = NULL;
    void *pvKey = NULL;
    va_list varList;

    if (NULL == (pvKey = malloc(ptHashMap->tKeyTypeInfo.nTypeSize)))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return -1;
    }

    va_start(varList, ptHashMap);
    if (_basContainerGetVaArgValue(&ptHashMap->tKeyTypeInfo, pvKey, &varList) != 0)
    {
        free(pvKey);
        CONTAINER_LOG_ERROR("_basContainerGetVaArgValue failed");
        return -1;
    }

    ptHashMapSlotFind = _basHashMapSearchHashSlot(ptHashMap, _basHashMapGetHashValue(ptHashMap, pvKey), pvKey);

    if (BUILDIN_STRING == ptHashMap->tKeyTypeInfo.iDataType)
    {
        ptHashMap->tKeyTypeInfo.pfnDestroy(pvKey);
    }
    free(pvKey);

    if (!IS_HASH_MAP_SLOT_EMPTY(*ptHashMapSlotFind))
    {
        _basHashMapRemoveHashSlot(ptHashMap, ptHashMapSlotFind);
        ptHashMap->uiUsed--;

        return 0;
    }
    else
    {
        return -1;
    }
}

BAS_EXPORT void *basHashMapFind(const T_HashMap *ptHashMap, ...)
{
    assert(ptHashMap != NULL);

    T_HashMapSlot *ptHashMapSlotFind = NULL;
    void *pvKey = NULL;
    va_list varList;

    if (NULL == (pvKey = malloc(ptHashMap->tKeyTypeInfo.nTypeSize)))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return NULL;
    }

    va_start(varList, ptHashMap);
    if (_basContainerGetVaArgValue(&ptHashMap->tKeyTypeInfo, pvKey, &varList) != 0)
    {
        free(pvKey);
        CONTAINER_LOG_ERROR("_basContainerGetVaArgValue failed");
        return NULL;
    }
    va_end(varList);

    ptHashMapSlotFind = _basHashMapSearchHashSlot(ptHashMap, _basHashMapGetHashValue(ptHashMap, pvKey), pvKey);

    if (BUILDIN_STRING == ptHashMap->tKeyTypeInfo.iDataType)
    {
        ptHashMap->tKeyTypeInfo.pfnDestroy(pvKey);
    }
    free(pvKey);

    return IS_HASH_MAP_SLOT_EMPTY(*ptHashMapSlotFind) ? NULL : ptHashMapSlotFind->pvValue;
}

BAS_EXPORT T_Iterator basHashMapBegin(const T_HashMap *ptHashMap)
{
    assert(ptHashMap != NULL);

    T_Iterator tIterator;
    T_HashMapSlot *ptHashMapSlot = NULL;

    for (ptHashMapSlot = &ptHashMap->taHashMapSlot[0];
         ptHashMapSlot < &ptHashMap->taHashMapSlot[ptHashMap->uiMask + 1];
         ++ptHashMapSlot)
    {
        if (!IS_HASH_MAP_SLOT_EMPTY(*ptHashMapSlot))
        {
            break;
        }
    }

    tIterator.tPos.pvBasicPos = (void *)ptHashMapSlot;
    tIterator.pvContainer = (void *)ptHashMap;
    tIterator.eIteratorType = ITERATOR_INPUT;
    tIterator.eContainerType = CONTAINER_HASH_MAP;

    return tIterator;
}

BAS_EXPORT T_Iterator basHashMapEnd(const T_HashMap *ptHashMap)
{
    assert(ptHashMap != NULL);

    T_Iterator tIterator;

    tIterator.tPos.pvBasicPos = (void *)&ptHashMap->taHashMapSlot[ptHashMap->uiMask + 1];
    tIterator.pvContainer = (void *)ptHashMap;
    tIterator.eIteratorType = ITERATOR_INPUT;
    tIterator.eContainerType = CONTAINER_HASH_MAP;

    return tIterator;
}

/**
 * @brief HashMap额外的迭代器有效性检查
 * @see   basIteratorIsValid
 */
static bool _basHashMapIteratorIsValid(const T_Iterator tIterator)
{
    T_HashMap *ptHashMap = (T_HashMap *)tIterator.pvContainer;

    if (tIterator.tPos.pvBasicPos > (void *)&ptHashMap->taHashMapSlot[ptHashMap->uiMask + 1] ||
        tIterator.tPos.pvBasicPos < (void *)&ptHashMap->taHashMapSlot[0])
    {
        return false;
    }

    return true;
}

/**
 * @brief HashMap实现的basIteratorGetValue
 * @see   basIteratorGetValue
 */
static void _basHashMapIteratorGetValue(const T_Iterator tIterator, void *pvValue)
{
    memcpy(pvValue, tIterator.tPos.pvBasicPos, sizeof(T_HashMapSlot));
}

/**
 * @brief HashMap实现的basIteratorGetPointer
 * @see   basIteratorGetPointer
 */
static void *_basHashMapIteratorGetPointer(const T_Iterator tIterator)
{
    return tIterator.tPos.pvBasicPos;
}

/**
 * @brief HashMap实现的basIteratorNext
 * @see   basIteratorNext
 */
static T_Iterator _basHashMapIteratorNext(const T_Iterator tIterator)
{
    T_Iterator tIteratorNext;
    T_HashMapSlot *ptHashMapSlot = NULL;

    memcpy(&tIteratorNext, &tIterator, sizeof(T_Iterator));

    for (ptHashMapSlot = (T_HashMapSlot *)tIterator.tPos.pvBasicPos + 1;
         ptHashMapSlot < ((T_HashMap *)(tIterator.pvContainer))->taHashMapSlot +
                         ((T_HashMap *)(tIterator.pvContainer))->uiMask + 1;
         ++ptHashMapSlot)
    {
        if (!IS_HASH_MAP_SLOT_EMPTY(*ptHashMapSlot))
        {
            break;
        }
    }
    tIteratorNext.tPos.pvBasicPos = (void *)ptHashMapSlot;

    return tIteratorNext;
}

/**
 * @brief HashMap实现的basIteratorEqual
 * @see   basIteratorEqual
 */
static bool _basHashMapIteratorEqual(const T_Iterator tFirstIterator, const T_Iterator tSecondIterator)
{
    return tFirstIterator.tPos.pvBasicPos == tSecondIterator.tPos.pvBasicPos;
}

/**
 * @brief     扩大HashMap的容量
 * @param[in] ptHashMap 指向HashMap的指针
 * @return    0 - 成功 -1 - 失败
 */
static int _basHashMapExpand(T_HashMap *ptHashMap)
{
    T_HashMapSlot *taOldHashMapSlot = ptHashMap->taHashMapSlot;
    T_HashMapSlot *ptHashMapSlotFind = NULL;
    unsigned int uiOldSize = ptHashMap->uiMask + 1;

    ptHashMap->uiMask = (ptHashMap->uiMask + 1) * BAS_MAP_EXPAND_MULTIPLICAND - 1;
    ptHashMap->uiLimit = (ptHashMap->uiMask + 1) * BAS_HASH_MAP_LOAD_FACTOR;

    if (NULL == (ptHashMap->taHashMapSlot = 
                 (T_HashMapSlot *)malloc(sizeof(T_HashMapSlot) * (ptHashMap->uiMask + 1))))
    {
        CONTAINER_LOG_ERROR("malloc failed");
        return -1;
    }
    memset(ptHashMap->taHashMapSlot, 0, sizeof(T_HashMapSlot) * (ptHashMap->uiMask + 1));

    for (unsigned int i = 0; i < uiOldSize; ++i)
    {
        if (!IS_HASH_MAP_SLOT_EMPTY(taOldHashMapSlot[i]))
        {
            ptHashMapSlotFind = _basHashMapSearchHashSlot(ptHashMap, taOldHashMapSlot[i].uiHashValue,
                                                          taOldHashMapSlot[i].pvKey);
            *ptHashMapSlotFind = taOldHashMapSlot[i];
        }
    }

    free(taOldHashMapSlot);

    return 0;
}

/**
 * @brief     移除HashMapSlot, 释放内存
 * @param[in] ptHashMap     指向HashMap的指针
 * @param[in] ptHashMapSlot 指向HashMapSlot的指针
 */
static void _basHashMapRemoveHashSlot(T_HashMap *ptHashMap, T_HashMapSlot *ptHashMapSlot)
{
    if (BUILDIN_STRING == ptHashMap->tKeyTypeInfo.iDataType)
    {
        ptHashMap->tKeyTypeInfo.pfnDestroy(ptHashMapSlot->pvKey);
    }
    if (ptHashMap->tValueTypeInfo.pfnDestroy != NULL)
    {
        ptHashMap->tValueTypeInfo.pfnDestroy(ptHashMapSlot->pvValue);
    }

    free(ptHashMapSlot->pvKey);
    free(ptHashMapSlot->pvValue);

    ptHashMapSlot->pvKey = HASH_SLOT_REMOVED;
    ptHashMapSlot->pvValue = NULL;
}

/**
 * @brief     根据关键字生成Hash值
 * @param[in] ptHashMap 指向HashMap的指针
 * @param[in] pvKey     指向关键字的指针(BUILDIN_STRING类型除外, 关键字实际是*(char **)pvKey, 而非pvKey)
 * @returns   Hash值
 */
static unsigned int _basHashMapGetHashValue(const T_HashMap *ptHashMap, const void *pvKey)
{
    if (BUILDIN_STRING == ptHashMap->tKeyTypeInfo.iDataType)
    {
        return ptHashMap->pfnHash(*(char **)pvKey, strlen(*(char **)pvKey));
    }
    else
    {
        return ptHashMap->pfnHash(pvKey, ptHashMap->tKeyTypeInfo.nTypeSize);
    }
}

/**
 * @brief     比较两个关键字是否相等
 * @param[in] ptHashMap 指向HashMap的指针
 * @param[in] pvKey1    指向关键字的指针(BUILDIN_STRING类型除外, 关键字实际是*(char **)pvKey, 而非pvKey)
 * @param[in] pvKey2    指向关键字的指针(BUILDIN_STRING类型除外, 关键字实际是*(char **)pvKey, 而非pvKey)
 * @return    0 - 相等 非0 - 不相等  
 */
static int _basHashMapCompareKey(const T_HashMap *ptHashMap, const void *pvKey1, const void *pvKey2)
{
    if (BUILDIN_STRING == ptHashMap->tKeyTypeInfo.iDataType)
    {
        return strcmp(*(char **)pvKey1, *(char **)pvKey2);
    }
    else
    {
        return memcmp(pvKey1, pvKey1, ptHashMap->tKeyTypeInfo.nTypeSize);
    }
}

/**
 * @brief     根据Hash值和关键字在HashMap中搜索存放位置
 * @param[in] ptHashMap   指向HashMap的指针
 * @param[in] uiHashValue Hash值
 * @param[in] pvKey       指向关键字的指针(BUILDIN_STRING类型除外, 关键字实际是*(char **)pvKey, 而非pvKey)
 * @returns   存放位置
 */
static T_HashMapSlot *_basHashMapSearchHashSlot(const T_HashMap *ptHashMap, const unsigned int uiHashValue,
                                                const void *pvKey)
{
    T_HashMapSlot *ptHashMapSlotFree = NULL;
    T_HashMapSlot *ptHashMapSlot = NULL;
    unsigned int uiSlot = uiHashValue & ptHashMap->uiMask;
    
    ptHashMapSlot = &ptHashMap->taHashMapSlot[uiSlot];

    if (NULL == ptHashMapSlot->pvKey)
    {
        return ptHashMapSlot;
    }
    else if (HASH_SLOT_REMOVED == ptHashMapSlot->pvKey)
    {
        ptHashMapSlotFree = ptHashMapSlot;
    }
    else if (uiHashValue == ptHashMapSlot->uiHashValue && 
             _basHashMapCompareKey(ptHashMap, ptHashMapSlot->pvKey, pvKey) == 0)
    {
        return ptHashMapSlot;
    }
    else
    {
        ptHashMapSlotFree = NULL;
    }

    //使用开放定址法避免碰撞, 探测公式为j = (5j + 1 + perturb) & mask; perturb >>= PERTURB_SHIFT;
    for (unsigned int uiPerturb = uiHashValue; ; uiPerturb >>= PERTURB_SHIFT)
    {
        uiSlot = ((uiSlot << 2) + uiSlot + uiPerturb + 1) & ptHashMap->uiMask;
        ptHashMapSlot = &ptHashMap->taHashMapSlot[uiSlot];
        if (NULL == ptHashMapSlot->pvKey)
        {
            return (NULL == ptHashMapSlotFree) ? ptHashMapSlot : ptHashMapSlotFree;
        }
        else if (HASH_SLOT_REMOVED == ptHashMapSlot->pvKey)
        {
            if (NULL == ptHashMapSlotFree)
            {
                ptHashMapSlotFree = ptHashMapSlot;
            }
        }
        else if (uiHashValue == ptHashMapSlot->uiHashValue &&
                 _basHashMapCompareKey(ptHashMap, ptHashMapSlot->pvKey, pvKey) == 0)
        {
            return ptHashMapSlot;
        }
    }
}

/** @} */
